package com.sheng.leetcode.year2022.swordfingeroffer.day28;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author liusheng
 * @date 2022/09/26
 *<p>
 * 剑指 Offer 38. 字符串的排列<p>
 *<p>
 * 输入一个字符串，打印出该字符串中字符的所有排列。<p>
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。<p>
 *<p>
 * 示例:<p>
 * 输入：s = "abc"<p>
 * 输出：["abc","acb","bac","bca","cab","cba"]<p>
 *<p>
 * 限制：<p>
 *<p>
 * 1 <= s 的长度 <= 8<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0038 {

    @Test
    public void test01() {
        String s = "abc";
        System.out.println(Arrays.toString(new Solution().permutation(s)));
    }
}
class Solution {
    Set<String> set = new HashSet<>();
    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        perm(c, 0);
        return set.toArray(new String[0]);
    }

    public void perm(char[] c, int n) {
        if (n == c.length - 1) {
            // n等于 c.length - 1 时，将当前数组添加到集合中
            set.add(new String(c));
        } else {
            for (int i = n; i < c.length; i++) {
                // 交换位置
                swap(c, n, i);
                // 递归
                perm(c, n + 1);
                // 回溯
                swap(c, n, i);
            }
        }
    }

    public void swap(char[] c, int i1, int i2) {
        char t = c[i1];
        c[i1] = c[i2];
        c[i2] = t;
    }
}
